#include <iostream>
#include <vector>
#include <algorithm>


struct ListNode
{
    int val;
    ListNode*next;
};

ListNode* list_merge(ListNode*&head1,ListNode*&head2)
{
    // 直接同时遍历两个链表，然后构造一个新链表出来
    ListNode*temp1 = head1;
    ListNode*temp2 = head2;

    // 创建哑节点来简化操作
    // 等我画一下就知分晓
    ListNode*dummy = new ListNode;
    dummy->next = nullptr;
    ListNode*main_ = dummy;
    
    // 首先是共同不空之前
    while (temp1&&temp2)
    {   
        if (temp1->val < temp2->val)
        {
            main_->next = temp1;
            main_ = main_->next;
            temp1 = temp1->next;
            main_->next = nullptr;
        }
        else 
        {
            main_->next = temp2;
            main_ = main_->next;
            temp2 = temp2->next;
            main_->next = nullptr;
        }
    }

    // 出现空节点了
    if (!temp1)
    {   
        main_->next = temp2;
        return dummy->next;
    }

    // 
    if (!temp2)
    {
        main_->next = temp1;
        return dummy->next;
    }
}

void add_node(ListNode*&head,int val)
{
    ListNode*node = new ListNode;
    node->val = val;
    node->next = nullptr;

    if (!head)
    {
        head = node;
        return ;
    }

    ListNode*temp = head;
    while (temp->next)
    {
        temp = temp->next;
    }

    temp->next = node;
}

void print_list(ListNode*head)
{
    ListNode*temp = head;
    while (temp)
    {
        std::cout<<temp->val<<" ";
        temp = temp->next;
    }
    std::cout<<"\n";
}

int main()
{
    ListNode*h1 = new ListNode;
    h1->val = 1;
    h1->next = nullptr;
    for (int i = 3;i < 10;i ++)
    {
        add_node(h1,i);
    }

    ListNode*h2 = new ListNode;
    h2->val = 1;
    h2->next = nullptr;             // 如果下一个节点不滞空，那么会？？？
    for (int i = 2;i < 11;i++)
    {
        add_node(h2,i);
    }

    print_list(h1);
    print_list(h2);
    ListNode*head = list_merge(h1,h2);

    print_list(head);
    return 0;
}